import java.util.List;
import java.util.LinkedList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


class 二叉树剪枝 {
    // 函数的意义：给你一个根结点，把根结点所指向的树中只有0的子树给去除
    public TreeNode pruneTree(TreeNode root) {
        // 递归的出口
        if (root == null) {
            return null;
        }
        // 处理左子树
        TreeNode left = pruneTree(root.left);
        // 如果左子树为null，就得"剪枝"
        if (left == null) {
            root.left = null;
        }
        // 处理右子树
        TreeNode right = pruneTree(root.right);
        // 如果右子树为null，就得"剪枝"
        if (right == null) {
            root.right = null;
        }
        // 处理当前结点
        if (left == null && right == null && root.val == 0) {
            return null;
        }
        return root;
    }
}


class 验证二叉搜索树 {
    // 使用一个变量来记录中序遍历的前一个数值
    long prev = Long.MIN_VALUE;
    // 函数的意义：给你一个root，判断其指向的树是否为二叉搜索树
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 判断左子树是否为二叉搜索树
        boolean left = isValidBST(root.left);
        if (!left) { // 如果为false，那么后面的就不需要判断了
            return false;
        }
        // 判断当前结点是否符合二叉搜索树的定义
        if (root.val > prev) {
            prev = root.val;
        } else {
            return false;
        }
        // 判断右子树是否为二叉搜索树
        boolean right = isValidBST(root.right);
        if (!right) { // 如果为false，那么后面的就不需要判断了
            return false;
        }
        return true;
    }
}


class 二叉树中第k小的元素 {
    // 函数的意义：找到root树的第k小的结点
    int count, ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs(root);
        return ret;
    }

    private void dfs(TreeNode root) {
        if (root == null || count == 0) {
            return;
        }
        dfs(root.left);
        if (--count == 0) {
            ret = root.val;
            return;
        }
        dfs(root.right);
    }
}


class 二叉树中的所有路径 {
    List<String> l;
    public List<String> binaryTreePaths(TreeNode root) {
        l = new LinkedList<>();
        StringBuilder path = new StringBuilder();
        dfs(root, path);
        return l;
    }

    private void dfs(TreeNode root, StringBuilder _path) {
        // 新创建一个path变量，虽然值一样，但是地址并不一样
        // 这样每次在递归修改的时候，并不会相互影响，而是自己新创建的对象
        StringBuilder path = new StringBuilder(_path);
        if (root.left == null && root.right == null) {
            path.append(root.val);
            l.add(path.toString());
            return;
        } else {
            path.append(root.val);
            path.append("->");
        }
        if (root.left != null) {
            dfs(root.left, path);
        }
        if (root.right != null) {
            dfs(root.right, path);
        }
    }
}